class Solution {
public:
    ListNode* sortList(ListNode* head) {
        list<int> lt;
        ListNode* pcur = head;
        while (pcur != NULL) {
            lt.push_back(pcur->val);
            pcur = pcur->next;
        }
        lt.sort();
        pcur = head;
        list<int>::iterator it = lt.begin();
        while (it != lt.end()) {
            pcur->val = *it;
            ++it;
            pcur = pcur->next;
        }
        return head;
    }
};

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        int sizei = matrix.size();
        int sizej = matrix[0].size();
        stack<pair<int, int>> pos;
        for (int i = 0; i < sizei; i++) {
            for (int j = 0; j < sizej; j++) {
                if (matrix[i][j] == 0) {
                    pos.push(make_pair(i, j));
                }
            }
        }
        while (!pos.empty()) {
            int x = pos.top().first;
            int y = pos.top().second;
            for (int i = 0; i < sizei; i++) {
                matrix[i][y] = 0;
            }
            for (int j = 0; j < sizej; j++) {
                matrix[x][j] = 0;
            }
            pos.pop();
        }
    }
};

class Solution {
public:
    int ans = 0;
    int resolution(TreeNode* root)
    {
        if (root == NULL) return -1;
        int l = resolution(root->left) + 1;
        int r = resolution(root->right) + 1;
        ans = max(ans, l + r);
        return max(r, l);
    }
    int diameterOfBinaryTree(TreeNode* root) {
        resolution(root);
        return ans;
    }
};

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left),
 * right(right) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        if (root == NULL)return {};
        list<TreeNode*> lt;
        lt.push_back(root);
        vector<vector<int>> vv;
        vector<int> tmp;
        tmp.push_back(root->val);
        while (!lt.empty()) {
            tmp.clear();
            list<TreeNode*>::iterator it = lt.begin();
            while (it != lt.end()) {
                tmp.push_back((*it)->val);
                ++it;
            }
            vv.push_back(tmp);
            int size = lt.size();
            for (int i = 0; i < size; i++) {
                TreeNode* node = lt.front();
                if (node->left != nullptr) lt.push_back(node->left);
                if (node->right != nullptr) lt.push_back(node->right);
                lt.pop_front();
            }
        }
        return vv;
    }
};

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int n = nums.size();
        int l = 1, r = n - 1, ans = -1;
        while (l <= r) {
            int mid = (l + r) / 2;
            int cnt = 0;
            for (int i = 0; i < n; i++) {
                cnt += nums[i] <= mid;
            }
            if (cnt <= mid) l = mid + 1;
            else {
                r = mid - 1;
                ans = mid;
            }
        }
        return ans;
    }
};